package 每日一题;

public class No132分割回文串II {

    /**
     * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
     * 返回符合要求的 最少分割次数 。
     *
     * 示例 1：
     * 输入：s = "aab"
     * 输出：1
     * 解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
     * 示例 2：
     * 输入：s = "a"
     * 输出：0
     * 示例 3：
     * 输入：s = "ab"
     * 输出：1
     *  
     *
     * 提示：
     * 1 <= s.length <= 2000
     * s 仅由小写英文字母组成
     */

    private char[] arr;
    private boolean[][] dp;

    public int minCut(String s) {
        this.arr=s.toCharArray();
        this.dp=new boolean[s.length()][s.length()];
        this.initValid();

        /**
         * 先得出回文子串left,right
         * 然后遍历每一层,得到每一层的最短切割次数
         */

        int[] resultDp=new int[dp.length];
        resultDp[0]=0;

        //[0,0]最少 [0,1]最少 [0,2]最少 [0,3]最少...
        for (int i = 1; i < arr.length; i++) {
            if(dp[0][i]){
                //整体直接是一个字符串
                resultDp[i]=0;
            }else{
                // [0,i]是不是回文串,那么就看 [1,i] [2,i] [3,i] [4,i] ...... [i-1,i-1]
                // 如果[1,i]可以,那就 dp[1,i]+1;
                resultDp[i]=resultDp[i-1]+1;//默认比上一位多切一刀,所以下面就无需 j等于i 了
                for (int j = 1; j < i; j++) {
                    if(dp[j][i]) {
                        //如果 [i,j]可以切割,那就将此区域与前面的区域割开,那么总切割次数就为
                        resultDp[i] = Math.min(resultDp[i], resultDp[j-1] + 1);
                    }
                }
            }
        }

        return resultDp[arr.length-1];
    }

    private void initValid(){
        for (int i = arr.length-1; i >= 0; i--) {
            dp[i][i]=true;
            for (int j = i+1; j < arr.length; j++) {
                if(arr[i]==arr[j]&&(j-i<2||dp[i+1][j-1])){
                    dp[i][j]=true;
                }
            }
        }
    }

    public static void main(String[] args) {
        No132分割回文串II n=new No132分割回文串II();
        int result = n.minCut("aabba");
        System.out.println(result);
    }

}
